#pragma once

#include <vector>

class Solution
{
public:
    std::vector<int> searchRange(const std::vector<int>& nums, int target) {
        if (nums.empty())
            return { -1, -1 };
        if (nums.front() == target && nums.back() == target)
            return {0, (int)nums.size() - 1};
        int left = lower_bound(nums, 0, nums.size() - 1, target);
        if (left < 0)
            return { -1, -1 };
        int right = upper_bound(nums, left, nums.size() - 1, target);
        if (right < 0)
            return { -1, -1 };
        return { left, right };
    }

private:
    int lower_bound(const std::vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums.at(mid) == target && (mid == left || nums.at(mid - 1) < target))
                return mid;
            if (nums.at(mid) < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }

    int upper_bound(const std::vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums.at(mid) == target && (mid == right || nums.at(mid + 1) > target))
                return mid;
            if (nums.at(mid) > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
};
